#ifndef DSU_H_
#define DSU_H_
/******Disjoint Set Union(并查集)******/

#include <string>
#include <vector>


namespace lxj
{
// 并查集模版(牛客)
// 路径压缩 + 小挂大
// 测试链接 : https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372
struct UnionFind {
    inline constexpr static int MAXN         = 1000001;
    inline static int           father[MAXN] = {};
    inline static int           size[MAXN]   = {};
    inline static int           stack[MAXN]  = {};
    inline static int           n            = 0;

    UnionFind(int n)
    {
        UnionFind::n = n;
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i]   = 1;
        }
    }

    // i号节点，往上一直找，找到代表节点返回！
    inline int find(int i)
    {
        int size = 0;
        while (i != father[i]) {
            stack[size++] = i;
            i             = father[i];
        }
        while (size > 0) {
            father[stack[--size]] = i;
        }
        return i;
    }

    inline bool isSameSet(int a, int b) { return find(a) == find(b); }

    inline void unionSet(int a, int b)
    {
        int fx = find(a);
        int fy = find(b);
        if (fx != fy) {
            if (size[fx] >= size[fy]) {
                size[fx] += size[fy];
                father[fx] = fy;
            }
            else {
                size[fy] += size[fx];
                father[fy] = fx;
            }
        }
    }
};
// 只有路径压缩的并查集
struct UnionFind2 {
    inline constexpr static int MAXN         = 200001;
    inline static int           father[MAXN] = {};
    inline static int           n            = 0;

    UnionFind2(int n)
    {
        UnionFind2::n = n;
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    inline int find(int i)
    {
        if (i != father[i]) father[i] = find(father[i]);
        return father[i];
    }

    inline bool isSameSet(int a, int b) { return find(a) == find(b); }

    inline void unionSet(int a, int b) { father[this->find(a)] = this->find(b); }
};

// 情侣牵手
// n对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手
// 人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的ID
// 情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)
// 返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起
// 每次交换可选择任意两人，让他们站起来交换座位
// 测试链接 : https://leetcode.cn/problems/couples-holding-hands/
inline int minSwapsCouples(std::vector<int>& row)
{
    int        len = row.size();
    UnionFind2 uf(len / 2);
    int        sets = len / 2;
    for (int i = 0, fx, fy; i < len; i += 2) {
        fx = uf.find(row[i] / 2);
        fy = uf.find(row[i + 1] / 2);
        if (fx != fy) sets--;
        uf.unionSet(row[i] / 2, row[i + 1] / 2);
    }
    return len / 2 - sets;
}

// 相似字符串组
// 如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等
// 那么称 X 和 Y 两个字符串相似
// 如果这两个字符串本身是相等的，那它们也是相似的
// 例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)；
// "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似
// 总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}
// 注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似
// 形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
// 给你一个字符串列表 strs列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。
// 返回 strs 中有多少字符串组
// 测试链接 : https://leetcode.cn/problems/similar-string-groups/
inline int numSimilarGroups(std::vector<std::string>& strs)
{
    int        n = strs.size();
    int        m = strs[0].size();
    UnionFind2 uf(n);
    int        sets = n;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (uf.find(i) != uf.find(j)) {
                int diff = 0;
                for (int k = 0; k < m && diff < 3; k++) {
                    if (strs[i][k] != strs[j][k]) diff++;
                }
                if (diff == 0 || diff == 2) {
                    int fx = uf.find(i);
                    int fy = uf.find(j);
                    if (fx != fy) sets--;
                    uf.unionSet(i, j);
                }
            }
        }
    }
    return sets;
}

// 岛屿数量
// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
// 此外，你可以假设该网格的四条边均被水包围
// 测试链接 : https://leetcode.cn/problems/number-of-islands/
class NumberOfIslands {
    inline constexpr static int MAXN         = 100001;
    inline static int           father[MAXN] = {};
    inline static int           sets         = 0;
    inline static int           cols         = 0;

public:
    inline void build(int n, int m, std::vector<std::vector<char>>& grid)
    {
        cols = m;
        sets = 0;
        for (int a = 0; a < n; a++) {
            for (int b = 0, index; b < m; b++) {
                if (grid[a][b] == '1') {
                    index         = this->index(a, b);
                    father[index] = index;
                    sets++;
                }
            }
        }
    }

    inline int index(int a, int b) { return a * cols + b; }

    inline int find(int i)
    {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    inline void unionSet(int a, int b, int c, int d)
    {
        int fx = find(index(a, b));
        int fy = find(index(c, d));
        if (fx != fy) {
            father[fx] = fy;
            sets--;
        }
    }

    inline int numIslands(std::vector<std::vector<char>>& grid)
    {
        int n = grid.size();
        int m = grid[0].size();
        build(n, m, grid);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    if (j > 0 && grid[i][j - 1] == '1') {
                        unionSet(i, j, i, j - 1);
                    }
                    if (i > 0 && grid[i - 1][j] == '1') {
                        unionSet(i, j, i - 1, j);
                    }
                }
            }
        }
        return sets;
    }
};
}   // namespace lxj

#endif